package com.cqs.leetcode.string;

import java.util.*;

/**
 * @author lixqw
 * @date 2020/9/10
 */
public class ReorganizeString {

    public String reorganizeString(String S) {
        if (S == null || S.length() <= 1) return S;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < S.length(); i++) {
            Character key = S.charAt(i);
            Integer value = map.getOrDefault(key, 0) + 1;
            //提前结束
            if (value * 2 > S.length() + 1) return "";
            map.put(key, value );
        }
        PriorityQueue<Map.Entry<Character, Integer>> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        priorityQueue.addAll(map.entrySet());
        StringBuilder sb = new StringBuilder();
        //贪心思想
        Character pre = null;
        Map.Entry<Character, Integer> tmp = null;
        while (priorityQueue.size() > 0) {
            Map.Entry<Character, Integer> peek = priorityQueue.peek();
            Character key = peek.getKey();
            //相同的元素不能相连
            if (key.equals(pre)) {
                if (priorityQueue.size() == 1) return "";
                //取第二大元素
                tmp = priorityQueue.poll();
                peek = priorityQueue.peek();
                key = peek.getKey();
            }
            sb.append(key);
            pre = key;
            //调整堆
            if (peek.getValue() == 1) {
                priorityQueue.poll();
            } else {
                peek.setValue(peek.getValue() - 1);
            }
            if (tmp != null) {
                priorityQueue.add(tmp);
                tmp = null;
            }
        }
        return sb.toString();
    }


    static class Solution{
        private String result = "";
        public String reorganizeString(String S) {
            result = "";
            dfs(S, 0, new boolean[S.length()], "");
            return result;
        }


        private void dfs(String s, int level, boolean[] used, String tmp) {
            //终止条件
            if (level == s.length()) {
                result = tmp;
                return;
            }
            //每个元素都要使用一次
            for (int i = 0; i < s.length(); i++) {
                //剪枝
                if (used[i] || (level > 0 && s.charAt(i) == tmp.charAt(level - 1))) continue;
                used[i] = true;
                dfs(s, level + 1, used, tmp + s.charAt(i));
                //回溯
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        ReorganizeString rs = new ReorganizeString();
        Solution solution = new Solution();
        List<String> tests = new ArrayList<>();
        tests.add("aba");
        tests.add("a");
        tests.add("aba");
        tests.add("aaaab");
        tests.add("aaaaabbbbc");
        tests.add("aaaaaabbbbc");
        //规模不能太大，否则递归次数太多
        tests.add("kkkkzrkatkwpkkkktrq");
        tests.forEach(it -> {
            String s = rs.reorganizeString(it);
            String sol = solution.reorganizeString(it);
            System.out.println(it + "\t" + s + "\t" + sol);
        });
    }

}
